//+------------------------------------------------------------------+
//|                                                   SortedSet.mqh |
//|                             Copyright 2000-2025, MetaQuotes Ltd. |
//|                                             https://www.mql5.com |
//+------------------------------------------------------------------+
#include <Generic/Interfaces/ISet.h>              // 继承集合接口 ISet<T>，获取基础集合能力
#include <Generic/Internal/Introsort.h>           // 内省排序工具（用于数组排序，支撑集合运算）
#include "RedBlackTree.h"                         // 红黑树类（底层存储，实现有序性与高效操作）
#include "HashSet.h"                              // 哈希集合类（用于集合关系判断，如子集/超集）

//+------------------------------------------------------------------+
//| CSortedSet<T> 类：有序集合实现类                                 |
//| 核心定位：实现 ISet<T> 接口，基于红黑树（CRedBlackTree<T>）作为底层存储， |
//|           按“元素排序规则”维护唯一元素，兼具集合的唯一性与有序性       |
//| 核心特性：                                                      |
//|  1. 元素唯一性：同一元素仅能存储一次，重复添加会失败（集合本质）；    |
//|  2. 有序性：所有元素按比较器规则（默认升序）有序存储，遍历/复制时按序输出； |
//|  3. 高效操作：插入/删除/查找/最值获取均为 O(log n) 时间复杂度（依赖红黑树）； |
//|  4. 集合运算：支持差集、交集、并集等数学集合操作（继承 ISet 接口）；    |
//|  5. 范围查询：支持按值范围提取子集（如获取 [10, 20] 之间的所有元素）；  |
//| 适用场景：所有需要“有序管理唯一元素”且需高效增删查的场景，典型如：    |
//|  - 有序去重数据（如按时间排序的唯一交易信号列表、去重后的日志等级集合）； |
//|  - 范围筛选场景（如筛选价格在 [100, 200] 之间的唯一品种代码）；        |
//|  - 有序统计维度（如按数值排序的唯一指标阈值集合、去重后的用户权限标识）； |
//|  - 集合运算与有序输出结合的场景（如求两个有序集合的交集并按升序输出）；  |
//+------------------------------------------------------------------+
template<typename T>
class CSortedSet : public ISet<T>
  {
protected:
   CRedBlackTree<T>* m_tree;  // 底层红黑树（存储集合元素，实现有序性、唯一性与高效操作）

public:
   //----------------------------------------------------------------
   // 构造与析构接口
   //----------------------------------------------------------------
   /**
    * @brief 默认构造函数：创建空有序集合，使用默认元素比较器（升序）
    * @note 默认比较器为 CDefaultComparer<T>，适配基础类型（int/double/string/datetime 等）的自然升序
    */
                     CSortedSet(void);

   /**
    * @brief 指定比较器构造函数：创建空有序集合，使用自定义元素比较器
    * @param comparer [in] 元素比较器（实现 IComparer<T> 接口，定义排序规则）
    * @example 按数值降序排序 → 传入 DescendingComparer 实例；按字符串长度排序 → 传入 StringLengthComparer 实例
    */
                     CSortedSet(IComparer<T>* comparer);

   /**
    * @brief 从集合构造：创建有序集合并复制指定集合的所有元素，使用默认比较器
    * @param collection [in] 源集合（实现 ICollection<T> 接口，如 ArrayList/HashSet）
    * @note 复制后自动去重（源集合重复元素仅保留一个），并按默认比较器规则排序
    */
                     CSortedSet(ICollection<T>* collection);

   /**
    * @brief 集合+比较器构造：创建有序集合并复制指定集合的所有元素，使用自定义比较器
    * @param collection [in] 源集合（实现 ICollection<T> 接口）
    * @param comparer [in] 元素比较器（实现 IComparer<T> 接口）
    * @note 复制后自动去重，并按自定义比较器规则排序
    */
                     CSortedSet(ICollection<T>* collection, IComparer<T>* comparer);

   /**
    * @brief 从数组构造：创建有序集合并复制指定数组的所有元素，使用默认比较器
    * @param array [in] 源数组（元素类型与 T 一致）
    * @note 复制后自动去重（数组重复元素仅保留一个），并按默认比较器规则排序
    */
                     CSortedSet(T &array[]);

   /**
    * @brief 数组+比较器构造：创建有序集合并复制指定数组的所有元素，使用自定义比较器
    * @param array [in] 源数组（元素类型与 T 一致）
    * @param comparer [in] 元素比较器（实现 IComparer<T> 接口）
    * @note 复制后自动去重，并按自定义比较器规则排序
    */
                     CSortedSet(T &array[], IComparer<T>* comparer);

   /**
    * @brief 析构函数：清理有序集合资源
    * @note 释放底层红黑树内存（红黑树会自动删除所有节点及元素）
    */
                    ~CSortedSet(void);

   //----------------------------------------------------------------
   // 元素添加接口
   //----------------------------------------------------------------
   /**
    * @brief 向有序集合中添加元素（继承自 ISet<T> 接口）
    * @param value [in] 待添加的元素（类型与 T 一致）
    * @return bool - 添加结果：true=添加成功（元素不存在）；false=添加失败（元素已存在）
    * @note 内部调用红黑树的 Add 方法，自动按比较器规则插入并去重
    */
   bool              Add(T value) { return(m_tree->Add(value)); }

   //----------------------------------------------------------------
   // 基础信息与包含性检查接口
   //----------------------------------------------------------------
   /**
    * @brief 获取有序集合中的元素数量（继承自 ISet<T> 接口）
    * @return int - 元素数量（≥0，空集合返回0）
    */
   int               Count(void) { return(m_tree->Count()); }

   /**
    * @brief 检查集合是否包含指定元素（继承自 ISet<T> 接口）
    * @param item [in] 待检查的元素（类型与 T 一致）
    * @return bool - 检查结果：true=元素存在；false=元素不存在
    * @note 内部调用红黑树的 Contains 方法，时间复杂度 O(log n)
    */
   bool              Contains(T item) { return(m_tree->Contains(item)); }

   /**
    * @brief 获取当前使用的元素比较器
    * @return IComparer<T>* - 比较器实例（NULL 表示未设置）
    */
   IComparer<T>*     Comparer(void) const { return(m_tree->Comparer()); }

   /**
    * @brief 安全获取集合中的最小元素（按比较器规则排序后的最小值）
    * @param min [out] 输出参数，接收最小元素（仅当返回 true 时有意义）
    * @return bool - 获取结果：true=获取成功（集合非空）；false=获取失败（集合空）
    * @note 最小元素为红黑树的最左子节点，时间复杂度 O(log n)
    */
   bool              TryGetMin(T &min) { return(m_tree->TryGetMin(min)); }

   /**
    * @brief 安全获取集合中的最大元素（按比较器规则排序后的最大值）
    * @param max [out] 输出参数，接收最大元素（仅当返回 true 时有意义）
    * @return bool - 获取结果：true=获取成功（集合非空）；false=获取失败（集合空）
    * @note 最大元素为红黑树的最右子节点，时间复杂度 O(log n)
    */
   bool              TryGetMax(T &max) { return(m_tree->TryGetMax(max)); }

   //----------------------------------------------------------------
   // 批量复制接口
   //----------------------------------------------------------------
   /**
    * @brief 将集合中的所有元素按“比较器排序规则”复制到外部数组（继承自 ISet<T> 接口）
    * @param dst_array [out] 目标数组（需提前分配空间，或由方法自动扩容）
    * @param dst_start [in] 目标数组的起始复制索引（默认从0开始）
    * @return int - 实际复制的元素数量（等于 Count()）
    * @note 复制顺序与集合排序规则一致（默认升序），无需额外排序
    */
   int               CopyTo(T &dst_array[], const int dst_start=0);

   //----------------------------------------------------------------
   // 清理与删除接口
   //----------------------------------------------------------------
   /**
    * @brief 清空集合中的所有元素（继承自 ISet<T> 接口）
    * @note 内部调用红黑树的 Clear 方法，删除所有节点及元素，重置集合状态（Count() 变为0）
    */
   void              Clear(void) { m_tree->Clear(); }

   /**
    * @brief 从集合中删除指定元素（继承自 ISet<T> 接口）
    * @param item [in] 待删除的元素（类型与 T 一致）
    * @return bool - 删除结果：true=删除成功（元素存在）；false=删除失败（元素不存在）
    * @note 内部调用红黑树的 Remove 方法，删除后自动维护树的有序性与平衡性
    */
   bool              Remove(T item) { return(m_tree->Remove(item)); }

   //----------------------------------------------------------------
   // 集合运算接口（继承自 ISet<T>，实现数学集合操作）
   //----------------------------------------------------------------
   /**
    * @brief 差集运算：从当前集合中移除与目标集合共有的元素（当前集合 = 当前集合 - 交集）
    * @param collection [in] 目标集合（实现 ICollection<T> 接口）
    * @example 当前集合={1,2,3}，目标集合={2,3,4} → 结果={1}
    */
   void              ExceptWith(ICollection<T>* collection);

   /**
    * @brief 差集运算：从当前集合中移除与目标数组共有的元素（参数为数组，功能同上）
    * @param array [in] 目标数组（元素类型与 T 一致）
    */
   void              ExceptWith(T &array[]);

   /**
    * @brief 交集运算：保留当前集合与目标集合的共有元素（当前集合 = 交集）
    * @param collection [in] 目标集合（实现 ICollection<T> 接口）
    * @example 当前集合={1,2,3}，目标集合={2,3,4} → 结果={2,3}
    */
   void              IntersectWith(ICollection<T>* collection);

   /**
    * @brief 交集运算：保留当前集合与目标数组的共有元素（参数为数组，功能同上）
    * @param array [in] 目标数组（元素类型与 T 一致）
    */
   void              IntersectWith(T &array[]);

   /**
    * @brief 对称差集运算：保留仅在当前集合或目标集合中存在的元素（当前集合 = (A-B)∪(B-A)）
    * @param collection [in] 目标集合（实现 ICollection<T> 接口）
    * @example 当前集合={1,2,3}，目标集合={2,3,4} → 结果={1,4}
    */
   void              SymmetricExceptWith(ICollection<T>* collection);

   /**
    * @brief 对称差集运算：保留仅在当前集合或目标数组中存在的元素（参数为数组，功能同上）
    * @param array [in] 目标数组（元素类型与 T 一致）
    */
   void              SymmetricExceptWith(T &array[]);

   /**
    * @brief 并集运算：合并当前集合与目标集合的所有元素（去重，当前集合 = A∪B）
    * @param collection [in] 目标集合（实现 ICollection<T> 接口）
    * @example 当前集合={1,2,3}，目标集合={2,3,4} → 结果={1,2,3,4}
    */
   void              UnionWith(ICollection<T>* collection);

   /**
    * @brief 并集运算：合并当前集合与目标数组的所有元素（去重，参数为数组，功能同上）
    * @param array [in] 目标数组（元素类型与 T 一致）
    */
   void              UnionWith(T &array[]);

   //----------------------------------------------------------------
   // 集合关系判断接口（继承自 ISet<T>，验证集合间的包含/相等关系）
   //----------------------------------------------------------------
   /**
    * @brief 判断当前集合是否为目标集合的真子集（A⊂B 且 A≠B）
    * @param collection [in] 目标集合（实现 ICollection<T> 接口）
    * @return bool - 判断结果：true=是真子集；false=不是
    * @note 真子集要求：当前集合所有元素都在目标集合中，且目标集合元素数量更多
    */
   bool              IsProperSubsetOf(ICollection<T>* collection);

   /**
    * @brief 判断当前集合是否为目标数组的真子集（参数为数组，功能同上）
    * @param array [in] 目标数组（元素类型与 T 一致）
    * @return bool - 判断结果
    */
   bool              IsProperSubsetOf(T &array[]);

   /**
    * @brief 判断当前集合是否为目标集合的真超集（A⊃B 且 A≠B）
    * @param collection [in] 目标集合（实现 ICollection<T> 接口）
    * @return bool - 判断结果：true=是真超集；false=不是
    * @note 真超集要求：目标集合所有元素都在当前集合中，且当前集合元素数量更多
    */
   bool              IsProperSupersetOf(ICollection<T>* collection);

   /**
    * @brief 判断当前集合是否为目标数组的真超集（参数为数组，功能同上）
    * @param array [in] 目标数组（元素类型与 T 一致）
    * @return bool - 判断结果
    */
   bool              IsProperSupersetOf(T &array[]);

   /**
    * @brief 判断当前集合是否为目标集合的子集（A⊆B，可与目标集合相等）
    * @param collection [in] 目标集合（实现 ICollection<T> 接口）
    * @return bool - 判断结果：true=是子集；false=不是
    * @note 子集要求：当前集合所有元素都在目标集合中（允许两者元素数量相同）
    */
   bool              IsSubsetOf(ICollection<T>* collection);

   /**
    * @brief 判断当前集合是否为目标数组的子集（参数为数组，功能同上）
    * @param array [in] 目标数组（元素类型与 T 一致）
    * @return bool - 判断结果
    */
   bool              IsSubsetOf(T &array[]);

   /**
    * @brief 判断当前集合是否为目标集合的超集（A⊇B，可与目标集合相等）
    * @param collection [in] 目标集合（实现 ICollection<T> 接口）
    * @return bool - 判断结果：true=是超集；false=不是
    * @note 超集要求：目标集合所有元素都在当前集合中（允许两者元素数量相同）
    */
   bool              IsSupersetOf(ICollection<T>* collection);

   /**
    * @brief 判断当前集合是否为目标数组的超集（参数为数组，功能同上）
    * @param array [in] 目标数组（元素类型与 T 一致）
    * @return bool - 判断结果
    */
   bool              IsSupersetOf(T &array[]);

   /**
    * @brief 判断当前集合与目标集合是否存在交集（是否有共同元素）
    * @param collection [in] 目标集合（实现 ICollection<T> 接口）
    * @return bool - 判断结果：true=存在交集；false=无交集
    */
   bool              Overlaps(ICollection<T>* collection);

   /**
    * @brief 判断当前集合与目标数组是否存在交集（参数为数组，功能同上）
    * @param array [in] 目标数组（元素类型与 T 一致）
    * @return bool - 判断结果
    */
   bool              Overlaps(T &array[]);

   /**
    * @brief 判断当前集合与目标集合是否完全相等（元素完全相同，忽略顺序）
    * @param collection [in] 目标集合（实现 ICollection<T> 接口）
    * @return bool - 判断结果：true=元素完全相同；false=存在差异
    * @note 相等判定条件：元素数量相同 + 所有元素互相包含
    */
   bool              SetEquals(ICollection<T>* collection);

   /**
    * @brief 判断当前集合与目标数组是否完全相等（参数为数组，功能同上）
    * @param array [in] 目标数组（元素类型与 T 一致）
    * @return bool - 判断结果
    */
   bool              SetEquals(T &array[]);

   //----------------------------------------------------------------
   // 有序集合特有接口（基于排序规则的扩展功能）
   //----------------------------------------------------------------
   /**
    * @brief 提取集合中“值在 [lower_value, upper_value] 范围内”的子集，复制到目标数组
    * @param array [out] 目标数组（存储范围子集元素，按集合排序规则排列）
    * @param lower_value [in] 范围下限（包含该值，按比较器规则判断）
    * @param upper_value [in] 范围上限（包含该值，按比较器规则判断）
    * @return bool - 提取结果：true=成功提取（存在符合范围的元素）；false=提取失败（无符合元素或范围无效）
    * @note 范围有效性：需满足 lower_value ≤ upper_value（按比较器规则），否则返回 false
    */
   bool              GetViewBetween(T &array[], T lower_value, T upper_value);

   /**
    * @brief 将集合元素按“与当前排序规则相反的顺序”复制到目标数组
    * @param array [out] 目标数组（存储逆序后的元素）
    * @return bool - 复制结果：true=逆序复制成功；false=复制失败（如数组内存不足）
    * @example 当前集合按升序排序为 {1,2,3} → 逆序后为 {3,2,1}
    */
   bool              GetReverse(T &array[]);
  };
//+------------------------------------------------------------------+